package cn.fansunion.leecode.isNumber;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 找出数组中的幸运数
 * 在整数数组中，如果一个整数的出现频次和它的数值大小相等，我们就称这个整数为「幸运数」。

给你一个整数数组 arr，请你从中找出并返回一个幸运数。

如果数组中存在多个幸运数，只需返回 最大 的那个。
如果数组中不含幸运数，则返回 -1 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-lucky-integer-in-an-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @author wen.lei@brgroup.com
 *
 * 2022-2-16
 */
public class FindLuckyIntegerInAnArray {
    
    /*    输入：arr = [2,2,3,4]
        输出：2
        解释：数组中唯一的幸运数是 2 ，因为数值 2 的出现频次也是 2 。
    
        输入：arr = [1,2,2,3,3,3]
        输出：3
        解释：1、2 以及 3 都是幸运数，只需要返回其中最大的 3 。
    
        输入：arr = [2,2,2,3,3]
        输出：-1
        解释：数组中不存在幸运数。
    
        输入：arr = [5]
        输出：-1
    
        输入：arr = [7,7,7,7,7,7,7]
        输出：7*/
    /**
     * 可读性第一位，方便代码复用；核心业务逻辑，单独维护
     * @param arr
     * @return
     */
    public int findLucky(int[] arr) {
        if(arr==null || arr.length==0) {
            return -1;
        }
        //每个数字的次数map，num-count
        Map<Integer,Integer> numCountMap=numCountMap(arr);
        List<Integer> allLuckyNumList=allLuckyNumList(arr,numCountMap);
        int maxLuckyNum=maxLuckyNum(allLuckyNumList);
        return maxLuckyNum;

    }

    /**
     * 从幸运数中返回最大的一个或者-1表示没有
     * @param allLuckyNumList
     * @return
     */
    private int maxLuckyNum(List<Integer> allLuckyNumList) {
        int max=-1;
        for (Integer luckyNum : allLuckyNumList) {
            if(luckyNum>max) {
                max=luckyNum;
            }
        }
        return max;
    }

    /**
     * 遍历数组，根据数字和出现的次数，找到所有的幸运数
     * @param arr
     * @param numCountMap
     * @return
     */
    private List<Integer> allLuckyNumList(int[] arr, Map<Integer, Integer> numCountMap) {
        List<Integer> allLuckyNumList = new ArrayList<>();
        for (int num : arr) {
            //此处不可能Null
            int count=numCountMap.get(num);
            if(num== count) {
                allLuckyNumList.add(num);
            }
        }
        return allLuckyNumList;
    }

    /**
     * 遍历数组，每个数字和对应的次数map
     * @param arr
     * @return
     */
    private Map<Integer, Integer> numCountMap(int[] arr) {
        Map<Integer, Integer> numCountMap = new HashMap<>();
        for (int num : arr) {
            Integer count=numCountMap.get(num);
            if(count==null) {
                count=1;
            }else{
                count++;
            }
            numCountMap.put(num, count);
        }
        return numCountMap;
    }
    
    //网友解法，代码极简；用数组代替map，取最大值，从后向前
    public int findLucky2(int[] arr) {
        int[] map = new int[501];
        for(int num : arr) map[num]++;
        for(int i=500; i>0; i--) 
            if(i==map[i])
                return i;

        return -1;
    }
}
